package com.jiangwz.bst;

/**
 * 二叉排序数
 *
 * @author jiangwz
 * @create 2019/10/8.
 */
public class BinarySortTreeDemo {

    public static void main(String[] args){
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree tree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            tree.addNode(new Node(arr[i]));
        }
        tree.inOrder();
        Node node = tree.search(10);
        System.out.println("-->"+node);

        //要求做到删除
    }
}

class BinarySortTree {
    private Node root;

    public void addNode(Node n) {
        if (n==null){
            return;
        }
        if (root == null) {
            root = n;
        }else {
            root.add(n);
        }
    }

    public void inOrder() {
        this.root.inOrder();
    }

    public Node search(int i) {
        if (root == null) {
            return null;
        }else {
            return root.search(i);
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public void add(Node node){
        if (node == null) {
            System.out.println("当前节点为空");
            return;
        }
        if (this.value > node.value) {
            if (this.left == null) {
                this.left = node;
            }else {
                this.left.add(node);
            }
        }else {
            if (this.right == null) {
                this.right= node;
            }else {
                this.right.add(node);
            }

        }
    }

    public void inOrder(){
        if (this.left != null) {
            this.left.inOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.inOrder();
        }
    }

    public Node search(int val){
        if (this.value == val) {
            return this;
        }
        Node res = null;
        if (this.left != null) {
            res = this.left.search(val);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.search(val);
        }
        return res;
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value='" + value + '\'' +
                '}';
    }
}
